//翻转对
class Solution {
public:
    vector<int> temp;
    void MergeSort(vector<int>& nums,int left , int right , int& ret)
    {
        if(left >= right) return;
        int mid = left + (right - left)/2;
        //[left , mid] [mid+1 , right]
        MergeSort(nums,left,mid,ret);
        MergeSort(nums,mid+1,right,ret);

        int cur1 = left , cur2 = mid+1 , i = 0;
        while(cur1 <= mid && cur2 <= right)
        {
            long long val = 2*static_cast<long long>(nums[cur2]);
            if(nums[cur1] > val)
            {
                ret += (mid - cur1 + 1);
                cur2++;
            }
            else 
            {
                cur1++;
            }
        }
        cur1 = left , cur2 = mid+1 , i = 0;
        while(cur1 <= mid && cur2 <= right)
            temp[i++] = nums[cur1] > nums[cur2] ? nums[cur2++] : nums[cur1++];
        while(cur1 <= mid) 
            temp[i++] = nums[cur1++];
        while(cur2 <= right)
            temp[i++] = nums[cur2++];

        for(int i = left ; i <= right ; ++i)
        {
            nums[i] = temp[i-left]; 
        }
    }
    int reversePairs(vector<int>& nums) {
        int n = nums.size();
        temp.resize(n);
        int ret = 0;
        MergeSort(nums,0,n-1,ret);
        return ret;
    }
};


